package com.zlsy.learning.leetcode.stack.s20;

import java.util.HashMap;
import java.util.Stack;

/**
 * @author zhouliang
 * @date 2020/8/10 20:03
 */
public class IsValid {

  private static HashMap<Character, Character> mappings;

  static {
    mappings = new HashMap<>();
    mappings.put(')', '(');
    mappings.put('}', '{');
    mappings.put(']', '[');
  }

  public static boolean isValid(String s) {
    Stack<Character> stack = new Stack<Character>();
    for (int i = 0; i < s.length(); i++) {
      // 初始化栈 S。
      char c = s.charAt(i);
      // 如果我们遇到一个闭括号，那么我们检查栈顶的元素。如果栈顶的元素是一个 相同类型的 左括号，
      // 那么我们将它从栈中弹出并继续处理。否则，这意味着表达式无效。
      if (mappings.containsKey(c)) {
        // 移除栈顶的对象，并且栈顶对象返回（也就是返回开括号）
        char topElement = stack.empty() ? '#' : stack.pop();
        // 通过c作为key去查找这个闭括号实际应该对应的开括号，如果相等就是对的，不等就返回false
        if (topElement != mappings.get(c)) {
          return false;
        }
      } else {
        // 如果遇到开括号，我们只需将其推到栈上即可。这意味着我们将稍后处理它，让我们简单地转到前面的 子表达式。
        stack.push(c);
      }
    }
    // 如果到最后我们剩下的栈中仍然有元素，那么这意味着表达式无效。
    return stack.isEmpty();
  }

  public static void main(String[] args) {
    String s = "()";
    boolean valid = isValid(s);
    System.out.println(valid);
  }
}
